/**
 * 
 */
package BNS.coloring;

import java.util.Vector;

import BNS.graphs.Edge;
import BNS.graphs.Graph;
import BNS.graphs.Node;

/**
 * @author Ian Gardner
 *
 */
public class SimuGraph {
	Vector<SimuNode> nodes;
	Vector<SimuEdge> edges;
	private final Vector<Vector<SimuNode>> neighbors;
	
	boolean colored;
	int largestClique;
	Vector<SimuNode> currentClique;
	
	/**
	 * Create a graph for Simulations from a normal graph.
	 * 
	 * @param gr - the normal Graph to copy to a SimuGraph
	 */
	public SimuGraph(Graph gr) {
		nodes=new Vector<SimuNode>(gr.getNodes().size());
		for(Node n:gr.getNodes())
			nodes.add(new SimuNode(n));
		
		edges=new Vector<SimuEdge>(gr.getEdges().size());
		for(Edge e:gr.getEdges()) 
			edges.add(new SimuEdge(nodes.get(e.from.getIndex()),nodes.get(e.to.getIndex())));
		
		colored = false;
		
		//create the vectors that will hold the neighbors of each node
		neighbors=new Vector<Vector<SimuNode>>();
		for(int i=0;i<nodes.size();i++)
			neighbors.add(new Vector<SimuNode>());
		
		//add node to to node from's neighbor vector
		//add node from to node to's neighbor vector
		for(SimuEdge e:edges) {
			neighbors.get(e.from.index).add(e.to);
			neighbors.get(e.to.index).add(e.from);
		}
	}
	
	/**
	 * Initialize the data structures of this graph, so that another simulation
	 * can be run without having to create a new graph.
	 */
	public void init() {
		for(SimuNode n:nodes)
			n.color=0;
		colored=false;
	}
	
	/**
	* Calculates whether a graph is well colored or not. I.E. whether every node
	* has a (non-white) color, and every edge has a different color at both ends.
	*  
	* @return - true for well colored, false otherwise
	*/
	public boolean wellColored() {
		if(colored) {
			for(SimuEdge edge:edges)
				if (edge.from.color == edge.to.color) return false;
			return true;
		}
	  	
	    //System.err.print("colored? checking: ");
	      //System.err.print("  " + node + ":" + node.color);
		for(SimuNode node:nodes)
			if (node.color == 0)
				return false;
	    //System.err.println();
		
		colored=true;
		return wellColored();
	}
	
	public void findClique() {
		currentClique=new Vector<SimuNode>();
		currentClique.add(nodes.get(0));
		
		System.out.println("The largest clique:"+largestClique(1));
	}
	
	//int cliqueSize;
	
	/**
	 * Finds the largest clique in this graph
	 */
	public int largestClique(int next) {
		int cliqueSize;
		int largestClique=0;
		if(next==nodes.size()) return 0;
		
		
		for(int i=next;i<nodes.size();i++) {
			if(inClique(nodes.get(i))) {
				currentClique.add(nodes.get(i));
				cliqueSize=1+largestClique(i+1);
				if(cliqueSize>largestClique) largestClique=cliqueSize;
			}
		}
		return largestClique;
	}
	
	public boolean inClique(SimuNode n) {
		for(SimuNode curr:currentClique)
			if(!neighbors.get(curr.index).contains(n))
				return false;
		
		return true;
	}
}
